# 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 
# 
#  请你将两个数相加，并以相同形式返回一个表示和的链表。 
# 
#  你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：l1 = [2,4,3], l2 = [5,6,4]
# 输出：[7,0,8]
# 解释：342 + 465 = 807.
#  
# 
#  示例 2： 
# 
#  
# 输入：l1 = [0], l2 = [0]
# 输出：[0]
#  
# 
#  示例 3： 
# 
#  
# 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
# 输出：[8,9,9,9,0,0,0,1]
#  
# 
#  
# 
#  提示： 
# 
#  
#  每个链表中的节点数在范围 [1, 100] 内 
#  0 <= Node.val <= 9 
#  题目数据保证列表表示的数字不含前导零 
#  
# 
#  Related Topics 递归 链表 数学 👍 10974 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, Link, LinkedListTool


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        """
        方法一
        cur = l1
        num1, num2 = 0, 0
        size = 0
        while cur:
            num1 += cur.val * 10 ** size
            size += 1
            cur = cur.next
        size = 0
        cur = l2
        while cur:
            num2 += cur.val * 10 ** size
            size += 1
            cur = cur.next

        s = list(str(num2 + num1))
        root = ListNode(val=int(s[-1]))
        cur = root
        for i in range(len(s)-2,-1,-1):
            cur.next = ListNode(val=int(s[i]))
            cur = cur.next

        return root
        """
        """
        方法二
        :param l1: 
        :param l2: 
        :return: 
        """
        dummy = ListNode(-1)
        curr = dummy
        # 如果上下相加满10了则需进一位，carry+=1
        carry = 0
        while l1 or l2 or carry:
            x1 = l1.val if l1 else 0
            x2 = l2.val if l2 else 0

            sum_num = x1 + x2 + carry
            carry = sum_num // 10
            # 创建结果链表
            val = sum_num % 10
            curr.next = ListNode(val=val)

            #           移动指针
            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next


# leetcode submit region end(Prohibit modification and deletion)
Link.each(Solution().addTwoNumbers(LinkedListTool([9, 9, 9, 9, 9, 9, 9]), LinkedListTool([9, 9, 9, 9])))
